Cyclic polytope

In mathematics, a cyclic polytope, denoted C(n,d), is a convex polytope formed as a convex hull of n distinct points on a rational normal curve in Rd, where n is greater than d. These polytopes were studied by Constantin Carathéodory, David Gale, Theodore Motzkin, Victor Klee, and others. They play an important role in polyhedral combinatorics: according to the Upper Bound Conjecture, proved by Peter McMullen and Richard Stanley, the boundary Δ(n,d) of the cyclic polytope C(n,d) maximizes the number fi of i-dimensional faces among all simplicial spheres of dimension d − 1 with n vertices.

Contents

Definition

The moment curve in \mathbb{R}^d is defined by

\mathbf{x}:\mathbb{R} \rightarrow \mathbb{R}^d, \mathbf{x}(t)�:= \begin{bmatrix}t\,t^2\,\ldots\,t^d\end{bmatrix}^T.

The d-dimensional cyclic polytope with n vertices is the convex hull

C(n,d)�:= \mathbf{conv}\{\mathbf{x}(t_1),\mathbf{x}(t_2),\ldots,\mathbf{x}(t_n) \}

of n > d \ge 2 distinct points \mathbf{x}(t_i) with t_1 < t_2 < \ldots < t_n on the moment curve.

The combinatorial structure of this polytope is independent of the points chosen, and the resulting polytope has dimension d and n vertices. Its boundary is a (d − 1)-dimensional simplicial polytope denoted Δ(n,d).

Gale evenness condition

The Gale evenness condition [1] provides a necessary and sufficient condition to determine a facet on a cyclic polytope.

Let T�:= \{t_1,t_2,\ldots,t_n\}. Then, a d-subset T_d \subseteq T forms a facet of C(n,d) iff any two elements in T \setminus T_d are separated by an even number of elements from T_d in the sequence (t_1,t_2,\ldots,t_n).

The upper bound conjecture

The number of i-dimensional faces of Δ(n,d) is given by the formula

f_i(\Delta(d,n)) = \binom{n}{i%2B1} \quad \textrm{for} \quad 0 \leq i < \left[\frac{d}{2}\right]

and (f_0,\ldots,f_{[\frac{d}{2}]-1}) completely determine (f_{[\frac{d}{2}]},\ldots,f_{d-1}) via the Dehn–Sommerville equations.

The Upper Bound Conjecture states that if Δ is a simplicial sphere of dimension d − 1 with n vertices , then

f_i(\Delta) \leq f_i(\Delta(n,d)) \quad \textrm{for}\quad i=0,1,\ldots,d-1.

The Upper Bound Conjecture for simplicial polytopes was proposed by Motzkin in 1957 and proved by McMullen in 1970. A key ingredient in his proof was the following reformulation in terms of h-vectors:

h_i(\Delta) \leq \tbinom{n-d%2Bi-1}{i} \quad \textrm{for} \quad 0 \leq i < \left[\frac{d}{2}\right].

Victor Klee suggested that the same statement should hold for all simplicial spheres and this was indeed established in 1975 by Stanley [2] using the notion of a Stanley–Reisner ring and homological methods

See also

References

  1. ^ Ziegler, Günter (1994). Lectures on Polytopes. Springer. pp. 14. ISBN 0-387-94365-X. 
  2. ^ Stanley, Richard (1996). Combinatorics and commutative algebra. Boston, MA: Birkhäuser Boston, Inc.. pp. 164. ISBN 0-8176-3836-9.